{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 Deutsch's Algorithm\n",
    "\n",
    "* [Q# exercise: Deutsch-Josza algorithm](./2-Quantum_Algorithms/2-Deutsch_s_Algorithm.ipynb#qex)\n",
    "\n",
    "This is one of the first algorithms to demonstrate the power of quantum computers. Developed by David\n",
    "Deutsch in the mid 80s, it determines if a function $f(x)$ is _Balanced_ ($f(0) \\ne f(1)$, which is 1-to-1) or\n",
    "_Constant_ ($f(0) = f()$, which is 2-to-1). Although it has no known applications, it serves as a starting\n",
    "point of future quantum algorithm developments.\n",
    "\n",
    "As we mentioned that quantum oracles (black boxes) are used in algorithms, let's begin by looking\n",
    "at four black boxes.\n",
    "\n",
    "_Constant 0_ black box (this will always return 0, whatever might be the input):\n",
    "\n",
    "<img src=\"img/2_d_c0.png\" style=\"width: 300px;\">\n",
    "\n",
    "_Constant 1_ black box (this will always return 1, whatever might be the input):\n",
    "\n",
    "<img src=\"img/2_d_c1.png\" style=\"width: 300px;\">\n",
    "\n",
    "\n",
    "_Balanced Same_ black box (the output will be the same as the input):\n",
    "\n",
    "<img src=\"img/2_d_b0.png\" style=\"width: 300px;\">\n",
    "\n",
    "\n",
    "\n",
    "_Balanced Reverse_ black box (the output will be the reverse of the input):\n",
    "\n",
    "<img src=\"img/2_d_b1.png\" style=\"width: 300px;\">\n",
    "\n",
    "\n",
    "Out of these four black boxes (two _Constant_ and two _Balanced_ ), you are given one without being informed\n",
    "which one it is. Your task is to identify whether it is a _Constant_ or a _Balanced_ one. This is what Deutsch's\n",
    "algorithm solves. You don't have to find which specific _Constant_ or _Balanced_ black box is given to you.\n",
    "\n",
    "<img src=\"img/2_d_d.png\" style=\"width: 300px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To solve this problem classically, you need to apply the black box twice to tell with 100%\n",
    "confidence whether it is a _Constant_ or a _Balanced_ one. Let's say you input a \"0\" to the black box. If it\n",
    "returns \"0\", the black box would have been _Constant 0_ or _Balanced Same_. You need run the black box\n",
    "again with input \"1\". If you get \"0\" as the output, then you can be sure that the black box is _Constant 0_ ;\n",
    "whereas if you get 1, you can be sure that the black box is _Balanced Same_.\n",
    "\n",
    "The same problem can be solved by just one execution of the black box using a quantum computer.\n",
    "First, we need to construct black boxes that are compatible with quantum logic. From the previous\n",
    "sections, we know that any quantum gate that implements a black box must be unitary (therefore\n",
    "reversible). Let's consider the truth table for _Constant 0_ black box:\n",
    "\n",
    "\n",
    "| $x$  | Constant 0: $f(x) = 0$ |\n",
    "| ---- | ---------------------- | \n",
    "|    0 | 0                      |\n",
    "|    1 | 0                      |\n",
    "\n",
    "It is apparent that it is impossible to construct any unitary matrix that takes \"$0$\" or \"$1$\" as input and gives\n",
    "\"$0$\" as the output because it is not reversible. However, we can construct a quantum oracle using the\n",
    "techniques discussed in the previous s</td><td>ssion:\n",
    "\n",
    "<img src=\"img/2_d_or.png\" style=\"width: 300px;\">\n",
    "\n",
    "Here $x$ and $y$ are each encoded with one qubit. Then the truth table for the above circuit for the _Constant_\n",
    "0 black box becomes:\n",
    "\n",
    "<table style=\"width: 350px; border: 1px solid black; text-align: center;\">\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <th style=\"border: 1px solid black;\"> $|x\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $|y\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $f(x)$ </th>\n",
    "    <th style=\"border: 1px solid black;, width: 50px;\"> $|y \\oplus f(x)\\rangle$ &nbsp; </th>\n",
    "</tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|1\\rangle$</td>\n",
    "    </tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|1\\rangle$</td>\n",
    "    </tr>\n",
    "    \n",
    "</table>\n",
    "\n",
    "$|y\\rangle$ and $|y \\oplus f(x) \\rangle$ are exactly the same (this happens to be the case only for _Constant 0_ scenario because $f(x) = 0$ always). So, the final quantum oracle for _Constant 0_ looks like:\n",
    "\n",
    "<img src=\"img/2_d_d2.png\" style=\"width: 300px;\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's construct the truth table for the _Constant_ 1 black box:\n",
    "\n",
    "<table style=\"width: 350px; border: 1px solid black; text-align: center;\">\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <th style=\"border: 1px solid black;\"> $|x\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $|y\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $f(x)$ </th>\n",
    "    <th style=\"border: 1px solid black;, width: 50px;\"> $|y \\oplus f(x)\\rangle$ &nbsp; </th>\n",
    "</tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|0\\rangle$</td>\n",
    "    </tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|0\\rangle$</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "\n",
    "In this case,  $|y \\oplus f(x) \\rangle$ is the reverse of $|y\\rangle$. From the previous sessions of this book, you have learned that this can be achieved by applying a Pauli X gate. So, we can construct the quantum oracle circuit as:\n",
    "\n",
    "<img src=\"img/2_d_d3.png\" style=\"width: 300px;\">\n",
    "\n",
    "Next, the truth table for _Balanced Same_ black box:\n",
    "\n",
    "<table style=\"width: 350px; border: 1px solid black; text-align: center;\">\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <th style=\"border: 1px solid black;\"> $|x\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $|y\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $f(x)$ </th>\n",
    "    <th style=\"border: 1px solid black;, width: 50px;\"> $|y \\oplus f(x)\\rangle$ &nbsp; </th>\n",
    "</tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|1\\rangle$</td>\n",
    "    </tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|0\\rangle$</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "\n",
    "You can observe here that $|y \\oplus f(x) \\rangle$ is matching with $|y \\rangle$ when $x = 0$ and is opposite to $|y \\angle$  when $x = 1$. This can be achieved by simply putting a CNOT between $x$ and $y$. We can construct the quantum oracle:\n",
    "\n",
    "<img src=\"img/2_d_d4.png\" style=\"width: 300px;\">\n",
    "\n",
    "\n",
    "For the _Balanced Reverse_ black box:\n",
    "\n",
    "\n",
    "<table style=\"width: 350px; border: 1px solid black; text-align: center;\">\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <th style=\"border: 1px solid black;\"> $|x\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $|y\\rangle$ </th>\n",
    "    <th style=\"border: 1px solid black;\"> $f(x)$ </th>\n",
    "    <th style=\"border: 1px solid black;, width: 50px;\"> $|y \\oplus f(x)\\rangle$ &nbsp; </th>\n",
    "</tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $1$    </td>\n",
    "    <td> $|0\\rangle$</td>\n",
    "    </tr>\n",
    "<tr  style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|0\\rangle$ </td>\n",
    "    </tr>\n",
    "<tr style=\"border: 1px solid black;\">\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $|1\\rangle$ </td>\n",
    "    <td> $0$    </td>\n",
    "    <td> $|1\\rangle$</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "This truth table is exactly the opposite to that of _Balanced Same._ So, we can use the same circuit we\n",
    "created for _Balanced Same_ and add an X gate at the end:\n",
    "\n",
    "<img src=\"img/2_d_d5.png\" style=\"width: 300px;\">\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have created all the four quantum black boxes, let's get into the actual Deutsch's\n",
    "algorithm. Consider an unknown (one of the four) black box and we construct the following circuit:\n",
    "\n",
    "<img src=\"img/2_d_deutsch.png\" style=\"width: 400px;\" title=\"Figure 2.1.3 Circuit representation of Deutsch's algorithm.\">\n",
    "\n",
    "\n",
    "_Figure 2.1.3 Circuit representation of Deutsch's algorithm._\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We prove in the insert below that by measuring just one qubit, we will know what kind of black box\n",
    "( _Constant_ or _Balanced_ ) it is.\n",
    "\n",
    "\n",
    ">_Math insert – Proof of Deutsch's algorithm for Constant black boxes_--------------------------\n",
    ">\n",
    ">The two-qubit system has an input $|0 \\rangle |0 \\rangle$. After applying X gate on the second qubit, the\n",
    ">system changes to $|0 \\rangle |1 \\rangle$. Applying H gates on both the qubits brings the state to\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} + \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\bigotimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \n",
    ">\\left( \\frac{|0 \\rangle}{\\sqrt 2}\\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2}\\right) -  \n",
    ">\\left( \\frac{|0 \\rangle}{\\sqrt 2}\\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2}\\right) +  \n",
    ">\\left( \\frac{|1 \\rangle}{\\sqrt 2}\\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2}\\right) -\n",
    ">\\left( \\frac{|1 \\rangle}{\\sqrt 2}\\right) \\left( \\frac{|1\n",
    ">\\rangle}{\\sqrt 2}\\right)$\n",
    ">\n",
    ">Applying the black box (applying $|x \\rangle |y \\rangle \\Rightarrow  |x \\rangle |y \\oplus f(x) \\rangle$ on all the four parts\n",
    ">in the superposition):\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |0   \\oplus   f(0) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |1   \\oplus   f(0) \\rangle}{\\sqrt 2} \\right) + \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |0   \\oplus   f(1) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |1   \\oplus   f(1) \\rangle}{\\sqrt 2} \\right)$\n",
    "> \n",
    ">$ = \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |f(0) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |1   \\oplus   f(0) \\rangle}{\\sqrt 2} \\right) + \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |f(1) \\rangle}{\\sqrt 2} \\right) - \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |1 \\oplus f(0) \\rangle}{\\sqrt 2} \\right)$\n",
    "> \n",
    "> (because $0 \\oplus f(0) = f(0)$ and $0 \\oplus f(1) = f(1)$ )\n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{  |f(0) \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{ \\overline{|f(0) \\rangle}}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{ \\overline{|f(1) \\rangle}}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{ \\overline{|f(1) \\rangle}}{\\sqrt 2} \\right)$ eq.(2.2.1)\n",
    ">   \n",
    "> (because $1 \\oplus f(0) = \\overline{f(0)}$ and $1 \\oplus f(1) = \\overline{f(1)}$ ).\n",
    "> \n",
    ">Let's evaluate the above result if the black box is _Constant 0_ (i.e. $f(0) = 0$ and $f(1) = 0$):\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|0 \\rangle}}{\\sqrt 2} \\right) +  \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|0 \\rangle}}{\\sqrt 2} \\right)$\n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) +  \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">Refactoring above:\n",
    ">\n",
    ">$ \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    ">  \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} + \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$.\n",
    ">   \n",
    ">Now, apply $H$ gate on the fuirst qubit:\n",
    ">\n",
    ">$| 0 \\rangle \\oplus \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$.\n",
    ">\n",
    ">We prove that if the given black box is Constant $0$, executing the above circuit and\n",
    ">measuring the first qubit will give $0$. But we haven't proven the converse - if we get $0$\n",
    ">after measuring the first qubit, does it mean that _Constant 0_ black box is used?\n",
    ">So, let's evaluate eq.(2.2.1) for Constant 1 (i.e. $f(0) = 1$ and $f(1) = 1$):\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right)\\left( \\frac{|f(0) \\rangle}{\\sqrt 2} \\right)- \n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right)\\left( \\frac{\\overline{|f(0) \\rangle}}{\\sqrt 2} \\right) +\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right)\\left( \\frac{|f(1) \\rangle}{\\sqrt 2} \\right)- \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right)\\left( \\frac{\\overline{|f(1) \\rangle}}{\\sqrt 2} \\right)$\n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|1 \\rangle}}{\\sqrt 2} \\right) + \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|1 \\rangle}}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) + \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right)$\n",
    ">   \n",
    ">After refactoring:\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2}  -  \\frac{|0 \\rangle}{\\sqrt 2} \\right) + \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2}  -  \\frac{|0 \\rangle}{\\sqrt 2} \\right)$\n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2}  +  \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2}  -  \\frac{|0 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2}  +  \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes\n",
    ">   - \\left( \\frac{|0 \\rangle}{\\sqrt 2}  -  \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= - \\left( \\frac{|0 \\rangle}{\\sqrt 2}  +  \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2}  -  \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">Applying $H$ gate on the first qubit:\n",
    ">\n",
    ">$- |0 \\rangle \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) $\n",
    ">\n",
    ">Here, if we measure the first qubit, it is 100% certain that we will still get $|0 \\rangle$, because\n",
    ">probability is the square of the amplitude ($-1$ in this case). So, we just proved that if the\n",
    ">given black box is _Constant 1_, executing the above circuit and measuring the first qubit\n",
    ">will give $0$.\n",
    "> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " We proved that for both scenarios ( _Constant_ 0 and _Constant_ 1), we will always get $|0 \\rangle$ at the end\n",
    "of the circuit if we measure the first qubit. This is what Deutsch's algorithm does. We can achieve it by\n",
    "just one execution of the black box (unlike classical black boxes for which two executions are needed). If\n",
    "we get 0, that means we have a _Constant_ black box. This is possible because of the superposition principle\n",
    "and gate execution on both states in parallel.\n",
    "\n",
    "However, we cannot be sure which exact black box it is because for the first scenario the first\n",
    "qubit is in $|0 \\rangle$ state and in the second scenario the first qubit is in $- |0 \\rangle$ state. It is impossible to distinguish these amplitudes (1 or -1). This is the limitation of the algorithm.\n",
    "\n",
    "Let's proceed with the remaining two black boxes.\n",
    "\n",
    ">_Math insert – Proof of Deutsch's algorithm for Balanced black boxes_--------------------------\n",
    ">\n",
    ">For _Balanced Same_ (i.e. $f(0) = 0$ and $f(1) = 1$) black box, eq. (2.2.1) becomes\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|f(0) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|f(0) \\rangle}}{\\sqrt 2} \\right) +\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|f(1) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|f(1) \\rangle}}{\\sqrt 2} \\right)$   \n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|0 \\rangle}}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|1 \\rangle}}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">Refactoring:\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|1 \\rangle}{\\sqrt 2} - \\frac{|0 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes - \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) -\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes - \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes\n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">Applying $H$ gate on the first qubit:\n",
    ">\n",
    ">$|1 \\rangle \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">We proved that if the given black box is _Balanced Same_ , executing the above circuit and\n",
    ">measuring the first qubit will give $1$.\n",
    ">For _Balanced Reverse_ (i.e. $f(0) = 1$ and $f(1) = 0$):\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|f(0) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|f(0) \\rangle}}{\\sqrt 2} \\right) +\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|f(1) \\rangle}{\\sqrt 2} \\right) -\n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|f(1) \\rangle}}{\\sqrt 2} \\right)$   \n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|1 \\rangle}}{\\sqrt 2} \\right) + \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{\\overline{|0 \\rangle}}{\\sqrt 2} \\right)$\n",
    ">   \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) +  \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) - \n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">   \n",
    ">Refactoring:\n",
    ">\n",
    ">$\\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right)  \\otimes \n",
    "> \\left( \\frac{|1 \\rangle}{\\sqrt 2} - \\frac{|0 \\rangle}{\\sqrt 2} \\right) + \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right)\n",
    "> \\otimes  \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    "> \n",
    ">$= \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes - \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes   \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) $ \n",
    ">\n",
    ">$= - \\left( \\frac{|0 \\rangle}{\\sqrt 2} \\right) \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) +\n",
    ">   \\left( \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes   \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) $ \n",
    ">\n",
    ">$= \\left( - \\frac{|0 \\rangle}{\\sqrt 2} + \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes \n",
    ">   \\left(   \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) $\n",
    ">\n",
    ">$= - \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) \\otimes \n",
    ">     \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right) $\n",
    ">\n",
    ">Applying $H$ gate on the first qubit:\n",
    ">\n",
    ">$- |1 \\rangle \\otimes \\left( \\frac{|0 \\rangle}{\\sqrt 2} - \\frac{|1 \\rangle}{\\sqrt 2} \\right)$\n",
    ">\n",
    ">We proved that if the given black box is _Balanced Reverse_ , executing the above circuit\n",
    ">and measuring the first qubit will always give $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This behavior is similar to the case of _Constant_ 0 and _Constant_ 1 black boxes - if the given black\n",
    "box is either _Balanced Same_ or _Balanced Reverse_ , executing the circuit and the first qubit will always result\n",
    "in |1⟩.\n",
    "\n",
    "To sum it up, by executing this circuit only once, if the measured output of the first qubits is 0, we\n",
    "can conclude that the given black box was either _Constant_ 0 or _Constant_ 1; and if the output is 1 then the\n",
    "given black box was either _Balanced Same_ or _Balanced Reverse_. The limitation with this algorithm is that\n",
    "it can tell if the given black box was _Constant_ or _Balanced_ but cannot tell the exact black box."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q# exercise: Deutsch's algorithm\n <a id='#qex'></a>",
    "\n",
    "1. Go to QuantumComputingViaQSharpSolution introduced in session 1.1.\n",
    "2. Open 21_Demo Deutsch's Algorithm Operation.qs in Visual Studio (Code).\n",
    "3. The black boxes are defined at the bottom of the script, starting from line 59, just as how we\n",
    "    constructed the circuit diagrams.\n",
    "\n",
    "![Figure Constant 0](img/Deutsch_exercise1.PNG)\n",
    "\n",
    "```\n",
    "    operation BlackBoxConstant0(qubits:Qubit[]):()\n",
    "    {\n",
    "        body\n",
    "        {\n",
    "            \n",
    "        }\n",
    "    }\n",
    "```\n",
    "\n",
    "![Figure Constant 1](img/Deutsch_exercise2.PNG)\n",
    "\n",
    "```\n",
    "    operation BlackBoxConstant1(qubits:Qubit[]):()\n",
    "    {\n",
    "        body\n",
    "        {\n",
    "            X(qubits[1]);\n",
    "        }\n",
    "    }\n",
    "```\n",
    "\n",
    "![Figure Balaced Same](img/Deutsch_exercise3.PNG)\n",
    "\n",
    "```\n",
    "    operation BlackBoxBalancedSame(qubits:Qubit[]):()\n",
    "    {\n",
    "        body\n",
    "        {\n",
    "            CNOT(qubits[0],qubits[1]);\n",
    "        }\n",
    "    }\n",
    "```\n",
    "\n",
    "![Figure Balaced Reverse](img/Deutsch_exercise4.PNG)\n",
    "\n",
    "```\n",
    "    operation BlackBoxBalancedDifferent(qubits:Qubit[]):()\n",
    "    {\n",
    "        body\n",
    "        {\n",
    "            X(qubits[0]);\n",
    "            CNOT(qubits[0],qubits[1]);\n",
    "        }\n",
    "    }\n",
    "```\n",
    "\n",
    "4.\tLine 27-30 allows us to choose which black box to use. Select one of the black boxes by commenting out the other three. Do dotnet run to check the results.\n",
    "\n",
    "```\n",
    "                //Apply the blackbox\n",
    "                //blackbox will set y = f(x) XOR y; which is same as CNOT(f(x),y)\n",
    "                //BlackBoxConstant0(qubits);\n",
    "                //BlackBoxConstant1(qubits);\n",
    "                //BlackBoxBalancedSame(qubits);\n",
    "                BlackBoxBalancedDifferent(qubits);\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.3 32-bit",
   "language": "qsharp",
   "name": "python38332bit225b1603132a4a1f9abff16033481403"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "3.8.3-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}